package com.future.interview;

import java.util.Stack;

/**
 * Description: 面试题 03.05. 栈排序
 * <p>
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
 * 该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sort-of-stacks-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/12/26 15:14
 */
public class Solution_0305 {
    public static void main(String[] args) {
        SortedStack obj = new SortedStack();
        obj.push(1);
        obj.push(2);
        obj.peek();
        obj.pop();
        obj.peek();
        boolean empty = obj.isEmpty();
        System.out.println();
    }

}


class SortedStack {

    Stack<Integer> mainStack;
    Stack<Integer> helpStack;

    public SortedStack() {
        mainStack = new Stack<Integer>();
        helpStack = new Stack<Integer>();
    }

    public void push(int val) {
        if (mainStack.isEmpty()) {
            mainStack.push(val);
        } else {
            while (!mainStack.isEmpty() && mainStack.peek() < val) {
                helpStack.push(mainStack.pop());
            }
            mainStack.push(val);
            while (!helpStack.isEmpty()) {
                mainStack.push(helpStack.pop());
            }
        }
    }

    public void pop() {
        if (!mainStack.isEmpty()) {
            mainStack.pop();
        }
    }

    public int peek() {
        if (!mainStack.isEmpty()) {
            return mainStack.peek();
        }
        return -1;
    }

    public boolean isEmpty() {
        return mainStack.isEmpty();
    }
}